#include "df.hpp"

#include <algorithm>
#include <list>
#include <stdio.h>
#include <string>
#include <stdlib.h>
#include <chrono>

using namespace std::chrono;
/* pour les mesures de temps d'éxecution */

/****************************** Exercice 1 : prise en main ********************/
data_t schema(const dfs_t& s){
//calcule l'ensemble des attributs qui apparaissent dans les DFs de s
  data_t r;
  auto first = s.cbegin();
  auto last = s.cend();

  /* /!\ COMPLETER CETTE FONCTION /!\ */
  for(;first != last; first++) {
    data_t src = (*first)._src;
    data_t dst = (*first)._dst;
  
    r.insert(src.begin(), src.end());
    r.insert(dst.begin(), dst.end());
  }

  return r;
}
/******************************************************************************/



/******************** Exercice 2 : fermeture naive ****************************/

data_t closure(const dfs_t &s, const data_t &x){
//calcule la fermeture d'un ensemble d'attributs vis-à-vis d'un ensemble de DFs
//avec l'algorithme naif. CET ALGORITHME EST FOURNI
  
  data_t r(x);
  
  //r est la fermeture courante que l'on va incrémenter.
  //on initialise r avec l'ensemble d'attributs que l'on veut fermer

  size_t i;  
 
  auto start = system_clock::now();

  do{
    i = r.size();
    for(auto it=s.cbegin() ; it !=s.cend() ; ++it){
    //pour chaque DF X->Y
      if(includes(r.cbegin(),r.cend(), it->_src.cbegin(), it->_src.cend())){
      //si la fermeture courante contient la partie gauche X
      //l'algorithme génrique includes est utilisé pour tester l'inclusion
      //http://www.cplusplus.com/reference/algorithm/includes/
  
          r.insert(it->_dst.cbegin(), it->_dst.cend());   
        //alors on ajoute la partie droit Y à la fermeture courante
        //on utilise la méthode insert de la classe set
        //http://www.cplusplus.com/reference/set/set/insert/
      }
    }    
  } while(i != r.size());
  
  //on repète la boucle tant qu'on a augmenté la fermeture lors du parcours des DFs
  
  auto stop = system_clock::now();

  auto elapsed = duration_cast<microseconds>(stop - start);

  cout << "temps de cloture nlin : " << elapsed.count() << "µs" << endl;

  return r;
  //on retourne la fermeture courante qui est saturée.
}

bool models(const dfs_t &s, const df_t &f){
//détermine si un ensemble de DFs en implique logiquement une autre en utilisant
//l'algorithme de fermeture : F |= X -> Y si et seulement si Y est inclus dans
//X+, la fermeture de X par F.
  data_t cloture_x;
  
  cloture_x = closure(s, f._src);

  if(includes(cloture_x.cbegin(), cloture_x.cend(), f._dst.cbegin(), f._dst.cend()))
    return true;
  else
    return false;
}

bool key(const dfs_t& s,const data_t &x){
//détermine si l'ensemble x est une clef en utilisant schema et closure

  data_t c = closure(s, x);
  data_t sc = schema(s);

  return(includes(c.begin(), c.end(), sc.begin(), sc.end()));
  // on retourne si l'ensemble des attribus de s est dans la fermeture de x par l'ensemble de DFs s  
}
/******************************************************************************/

/********************** Exercice 3 : fermeture linéaire ***********************/
count_t buildcount(const dfs_t &s){
//analyse l'ensemble de dfs s pour compter le nombre d'attributs de sa partie gauche
  count_t count; 
  //typedef  vector<size_t> count_t;
  
  for(auto it=s.begin(); it != s.end(); it++) {
    count.push_back(it->_src.size());
  }

  return count;
}

index_t buildindex(const dfs_t &s){
//analyse l'ensemble de dfs s pour construire l'index <attribut vers DF> associé.
  index_t idx;
  //map<att_t,list<size_t> > index_t;
  
  pair<index_t::iterator, bool> ajout;
  int ind = 0;

  for(auto it_dfs = s.begin(); it_dfs != s.end(); it_dfs++){
    for(auto it_df = it_dfs->_src.begin(); it_df != it_dfs->_src.end(); it_df++){
      
      list<size_t> df;
      df.push_back((size_t)ind);
         
      ajout = idx.insert(pair<att_t, list<size_t> >((*it_df), df));

      if(!ajout.second) {
        ajout.first->second.push_back((size_t)ind);
      }
    ind++;
   }
  }
  
  return idx;
}

data_t closurelin(const dfs_t &s, const data_t &x, const index_t &idx){
//calcule la fermeture d'un attribut vis-à-vis d'un ensemble de DFs
//version linéaire : s'appuie sur un index crée via buildindex
  
  data_t r(x);
  count_t count = buildcount(s);
  
  /* /!\ COMPLETER CETTE FONCTION /!\ */
  data_t up(x);

  att_t tmp_att;
  df_t tmp_df;
  data_t tmp_data;
  data_t tmp_data2;

  auto start = system_clock::now();

  while(!up.empty()) {
    /* on récupère le premier attribut de l'ensemble update, et on l'enleve de cet ensemble */
    tmp_att = (*up.begin());
    up.erase(up.begin());
    
    /* cout << "tmp_att = " << tmp_att << endl; */

    auto it_idx = idx.find(tmp_att); 
    if(it_idx != idx.end()) {

      list<size_t> liste = it_idx->second;
      for(auto it_l = liste.begin(); it_l != liste.end(); it_l++){
        count[(*it_l)]--;
        if(count[(*it_l)] == 0){
          tmp_df = s[(*it_l)];
          tmp_data = tmp_df._dst;
          tmp_data2 = tmp_data;
          
          for(auto it_erase = r.begin(); it_erase != r.end() ; it_erase++) {
            tmp_data2.erase(*it_erase);
          }

          up.insert(tmp_data2.begin(), tmp_data2.end());
          r.insert(tmp_data.begin(), tmp_data.end());      
          /* cout << "update : " << up << endl; */
         /* cout << "closure : " << r << endl << endl; */
        }
      }
    }
  }

  auto stop = system_clock::now();



  auto elapsed = duration_cast<microseconds>(stop - start);

  /* Décommenter cette ligne pour afficher le temps de calcul */
  std::cout << "temps de cloture lin : " << elapsed.count() << "µs" << endl;

  return r;


}

/******************************************************************************/

/***************** Exercice 4 : génération d'ensemble de dfs ******************/

dfs_t generate(size_t n){
//génère un ensemble de DFs de la forme {n-1 -> n, n-2 -> n-1, ..., 0 -> 1}
 

  dfs_t s; 
 /* 
  for(unsigned int i=1; i<=n; i++)
  {
    df_t tmp({to_string(n-i)},{to_string(n-(i-1))});
    cout << tmp << endl;
    s.push_back(tmp); // on insere pas Ã  pas les dfs :D 
  }
*/

  for(unsigned int i = n; i > 0; i--) {
    df_t tmp({to_string(i-1)},{to_string(i)});
    s.push_back(tmp);      
  }
  
  return s;
}
/******************************************************************************/


